The present invention relates to data processor memories, and in particular, the present invention relates to a method and apparatus for improving the speed in which memory is accessed.
In general, data processing systems comprise a central processing unit (CPU) that executes instructions that are fetched from a main memory. One method to improve the performance of the CPU is to use cache memory. Cache memory is high speed memory that works in conjunction with the CPU and the main memory to provide the necessary data to the CPU. With this architecture, a lower latency response time is possible than if the CPU fetches all instructions and operands directly from main memory. The improved performance is possible because the cache contains the data that the CPU is most likely to request in the near future. The cache is typically also much faster than the main memory, therefore, the cache can usually provide the data required by the CPU much faster than the main memory. Part of the methodology used to load data into the cache is to predict and store the data that is frequently used by the CPU and is likely to be used by the CPU in the near future.
One type of cache memory is organized into a structure known as an xe2x80x9cassociativexe2x80x9d structure (also referred to as xe2x80x9cset associativexe2x80x9d). In an associative structure, the blocks of storage locations are accessed as arrays having rows (often referred to as xe2x80x9csetsxe2x80x9d) and columns (often referred to as xe2x80x9cwaysxe2x80x9d). When a cache is searched for bytes residing at an address, a number of bits from the address are used as an xe2x80x9cindexxe2x80x9d into the cache. The index selects a particular set within the array, and therefore the number of address bits required for the index is determined by the number of sets configured into the cache. The act of selecting a set via an index is referred to as xe2x80x9cindexingxe2x80x9d. The addresses associated with bytes stored in the multiple ways of a set are examined to determine if any of the addresses stored in the set match the requested address. If a match is found, the access is said to be a xe2x80x9chitxe2x80x9d, and the cache provides the associated bytes. If a match is not found, the access is said to be a xe2x80x9cmissxe2x80x9d. When a miss is detected, the bytes are transferred from the memory system into the cache. The addresses associated with bytes stored in the cache are also stored. These stored addresses are referred to as xe2x80x9ctagsxe2x80x9d or xe2x80x9ctag addressesxe2x80x9d.
The blocks of memory configured into a set form the columns of the set. Each block of memory is referred to as a xe2x80x9cwayxe2x80x9d; multiple ways comprise a set. The way is selected by providing a way value to the cache. The way value is determined by examining the tags for a set and finding a match between one of the tags and the requested address. A cache designed with one way per set is referred to as a xe2x80x9cdirect-mapped cachexe2x80x9d. In a direct-mapped cache, the tag must be examined to determine if an access is a cache hit, but the tag examination is not required to select which bytes are transferred to the outputs of the cache. Since only an index is required to select bytes from a direct-mapped cache, the direct-mapped cache is a xe2x80x9clinear arrayxe2x80x9d requiring only a single value to select a storage location within it.
The hit rate in a data cache is important to the performance of a data processing system because when a miss is detected the data must be fetched from the memory system. The microprocessor will quickly become idle while waiting for the data to be provided. Set-associative caches require more access time than direct-mapped caches since the tags must be compared to the requested address and the resulting hit information must then be used to select which data bytes should be conveyed out of the data cache. As the clock frequencies of data processing systems increase, there is less time to perform the tag comparison and way selection. Therefore, there is a need for a data cache having the advantages of a set-associative cache with faster access times.